package acwing._1_1AlgorithmBasic;
/**
 * @Project : AlgorithmLearning
 * @Package : ACWing._1_1AlgorithmBasic
 * @File : _3_5BipartiteGraph.java
 * @Author : WangRuoyu
 * @Date : 2023/4/3 14:45
 */

public class _3_5BipartiteGraph {
    /*******染色法判断一个图是不是二分图*******/
    static boolean dfs(int u, int color, int st[], int[] h, int[] e, int[] next) {
        st[u] = color;
        for (int i = h[u]; i != -1; i = next[i]) {
            int j = e[i];
            if (st[j] == 0) { // 如果没染色就染色
                if (!dfs(j, -color, st, h, e, next)) return false;
            } else if (st[j] == color) { // 如果染过色就看颜色是否一致
                return false;
            }
        }
        return true;
    }

    /*******匈牙利算法求二分图的最大匹配*******/
    static boolean find(int u, int[] h, int[] e, int[] next, int[] match, boolean[] st) {
        for (int i = h[u]; i != -1; i = next[i]) {
            int j = e[i];
            if (!st[j]) {
                st[j] = true;
                if (match[j] == 0 || find(match[j], h, e, next, match, st)) {
                    match[j] = u;
                    return true;
                }
            }
        }
        return false;
    }
}

